; Exercise 1.25
; Alyssa P. Hacker complains that we went to a lot of extra work in writing 
; expmod. After all, she says, since we already know how to compute
; exponentials, we could have simply written
      (define (expmod base exp m)
         (remainder (fast-expt base exp) m))
; Is she correct? Would this procedure serve as well for our fast prime tester?
; Explain.

(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))

(define (expmodx base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmodx base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmodx base (- exp 1) m))
                    m))))

; Ela não está correta. Enquanto a nova função calcula o valor de um
; exponencial módulo outro número, ela é menos eficiente pois deixa de
; aproveitar propriedades da função módulo quando aplicada em um exponencial.
; Ao fazer isto a função fica muito lenta e o teste rápido demora mais que
; o teste original.
